# 25/100 链表-环形链表
# leetcode第141题: https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/16
from typing import Optional
from leetcode import test
from leetcode.bds import ListNode


def hasCycle(head: Optional[ListNode]) -> bool:
    if not head:
        return False
    curr = head
    visited = set()
    visited.add(head)
    while curr.next:
        if curr.next in visited:
            return True
        else:
            visited.add(curr.next)
            curr = curr.next
    return False


def hasCycle_dbpnt(head: Optional[ListNode]) -> bool:
    """使用快慢指针的方法, 只使用 O(1) 空间"""
    if not head:
        return False

    fast = head
    slow = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast is slow:
            return True
    return False


if __name__ == '__main__':
    head1 = ListNode(3)
    pos = head1.append(2)
    tail = pos.append(0).append(-4)
    tail.next = pos

    head2 = ListNode(1)
    pos = head2.append(2)
    pos.next = head2

    head3 = ListNode(1)

    head4 = ListNode(1)
    head4.append(2)

    inp = [{"head": head1}, {"head": head2}, {"head": head3}, {"head": head4}]
    out = [True, True, False, False]

    test.test_function(hasCycle, inp, out)
    test.test_function(hasCycle_dbpnt, inp, out)
